package likou

import (
	"math"
)

//https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence/

func SplitIntoFibonacci(num string) []int {
	var dfs func(int) bool
	var rst = make([]int, 0)

	dfs = func(idx int) bool {
		// 终止条件
		if idx == len(num) {
			// 至少元素要 大于等于 3， 才符合题目 fibonacci 的定义
			return len(rst) >= 3
		}

		curNum := int64(0)
		for i := idx; i < len(num); i++ {
			// 剪枝，判断当前是否是fibonacci数
			// 如果当前字符是 '0' 的话，则不做处理，因为数字不能以 0 开头
			if i > idx && num[idx] == '0' {
				continue
			}
			// 0. 求当前数字， 可能超过长度，所以是 int64
			curNum = curNum * 10 + int64(num[i] - '0')
			// 1. 如果大于32位，就直接结束循环，因为后面的数，一定更大
			if curNum > math.MaxInt32 {
				break
			}
			// 转换为 int
			var numm = int(curNum)
			// 2. 如果当前的 rst 长度大于2， 可以进行判断 curNum 是否符合条件
			if len(rst) >= 2 {
				prevTwoNumSum := int64(rst[len(rst)-1] + rst[len(rst)-2])
				if prevTwoNumSum > math.MaxInt32 {
					break
				}
				TwoNumSum := int(prevTwoNumSum)

				// 如果大于，直接结束循环
				if numm > TwoNumSum {
					break
				} else if numm < TwoNumSum {
					continue
				}
			}
			rst = append(rst, numm)
			// 3. 如果找了到 直接返回
			if dfs(i + 1) {
				return true
			}
			// 4. 回溯，删除添加的元素
			rst = rst[: len(rst) - 1]
		}

		return false
	}

	dfs(0)
	return rst
}